package q76_minWindow;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public static void main(String[] args) {
        String s = "cabwefgewcwaefgcf";
        String t = "cae";

        Solution solution = new Solution();
        System.out.println(solution.minWindow(s,t));

        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
        }

        Map<String, Integer> map1 = new HashMap<String, Integer>();
        map1.put("a", 1);
        map1.put("b", 2);


        Map<String, Integer> map2 = new HashMap<String, Integer>();
        map2.put("b", 2);
        map2.put("a", 1);

        // map之间的比较应该使用equals
        // System.out.println(map1.equals(map2));
    }

    /**
     * 个人解法：耗时和内存消耗都过高了
     * 但是和官方解法思路相同
     * 思路：滑动窗口（核心思路）
     * 首先将所有t中的字符存放在一个map之中，再新建一个sMap，然后开始从s的开头开始检测：
     * 如果有t中的字符，那么sMap也添加这个字符为key且value加一，
     * 当首次sMap中包含所有t中字符且数量都大于tMap中对应的value时
     * （为什么不是等于？因为有可能出现sMap已经存入tMap一部分字符并且value大于tMap中的值，但是仍然有一个字符没存到sMap，
     * 当其存进来的时候，其他字符的数量已经超过了tMap中的值）
     * 我们就先将对应的字符串存进来，在这一步如何判断对应的字符串，首先字符串两端一定是在t中的字符，如果有多余显然不对
     * 所以每一次向sMap中存入字符的时候，都有一个数组和bin在记录这次存入的字符是什么以及它的位置，也就是左指针在的位置
     * 右指针的位置显然就是i了，因为在i的时候恰好存入了t中的字符才能够使得我们开始记录字符串
     * 如此一来就形成了一个窗口，那么当第一次满足条件的字符串被存入之后，我们首先删除掉最左边的一个字符，找出下一个窗口看是否符合条件
     * 举例：例如我们sMap存入了这样一串字符串 aaabc 而t是 abc，到达c的时候我们才开始满足条件，我们就需要删除最左边的a
     * 然后看aabc是否也满足，如果满足则更新result，不满足意味着我们要继续i++，例如abcda 和 abc 我们会删除a 并继续寻找一直到bcda
     * 如此循环反复，最终能够找到最短的一串符合条件的字符串
     */
    public String minWindow(String s, String t) {
        if (s.length() < t.length()){
            return "";
        }

        // 首先用一个tMap存入所有t中的字符
        Map<Character, Integer> tMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
        }

        // sMap就是我们所使用的滑动窗口字典
        Map<Character, Integer> sMap = new HashMap<>();

        int[] record = new int[s.length()];
        int l = 0, r = 0;
        int rec = 0, index = 0;

        String result = "";
        String bin = "";
        for (int i = 0; i < s.length(); i++) {

            // sMap中只加入在t中的字符
            if (t.contains(s.charAt(i) + "")) {
                // 记录对应字符的位置
                record[rec] = i;
                rec ++;
                // 以及加入的字符是什么
                bin += s.charAt(i);

                sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i), 0) + 1);
            }


            // 当满足要求的时候，就开始操作窗口
            while (judgeMap(sMap,tMap)) {
                l = record[index];
                r = i;
                if (result.equals("")){
                    result = s.substring(l,r + 1);
                }
                result = result.length() > (r - l + 1) ? s.substring(l,r + 1) : result;

                // 记录一次res就删除窗口最左边的并且是在t中的一个字符，这个时候就用到了之前的bin和record
                sMap.put(bin.charAt(index),sMap.getOrDefault(bin.charAt(index), 0) - 1);
                index++;
            }

        }
        return result;
    }

    /**
     * 判断sMap中的所有对应字符是否大于等于了tMap中的对应字符
     */
    private static boolean judgeMap(Map<Character,Integer> sMap, Map<Character,Integer> tMap){
        for (Character character : tMap.keySet()) {
            if (sMap.get(character) == null || sMap.get(character) < tMap.get(character)){
                return false;
            }
        }
        return true;
    }
}
